# leetcode 239 滑动窗口最大值

class MyQueue:
    # 单调队列，从大到小
    def __init__(self):
        self.data = []

    def push(self, x):
        # 加入元素前，判断加入的元素与队列中的元素，比当前元素小的全部弹出，然后将x加入
        while len(self.data) != 0 and x > self.data[-1]:
            self.data.pop()
        self.data.append(x)

    def pop(self, x):
        # 当弹出的元素等于出口处的元素，才弹出
        if len(self.data) != 0 and x == self.data[0]:
            return self.data.pop(0)

    def get_max(self):
        # 出口处即队列最大值
        return self.data[0]

    def top(self):
        return self.data[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        queue = MyQueue()
        result = []
        n = len(nums)
        for i in range(k):
            queue.push(nums[i])
        result.append(queue.top())
        for j in range(k, n ):
            queue.pop(nums[j - k])
            queue.push(nums[j])
            result.append(queue.top())
        return result
